6.4 KB · ⇊ 4 parts · ⤓ Micron 6.4 KB · ⤓ HTML 18.0 KB

top

Algorithmic Puzzles is a book of puzzles based on computational thinking. It was written by computer scientists Anany and Maria Levitin, and published in 2011 by Oxford University Press.

• Topics

• Audience and reception

• References

The book begins with a "tutorial" introducing classical algorithm design techniques including backtracking, divide-and-conquer algorithms, and dynamic programming, methods for the analysis of algorithms, and their application in example puzzles.cite-ref-gasarch-1-0[1]cite-ref-rosebrock-2-0[2] The puzzles themselves are grouped into three sets of 50 puzzles, in increasing order of difficulty. A final two chapters provide brief hints and more detailed solutions to the puzzles,cite-ref-rosebrock-2-1[2] with the solutions forming the majority of pages of the book.cite-ref-griffiths-3-0[3]

Some of the puzzles are well known classics, some are variations of known puzzles making them more algorithmic, and some are new.cite-ref-narayanan-4-0[4] They include:

• Puzzles involving chessboards, including the eight queens puzzle, knight's tours, and the mutilated chessboard problemcite-ref-gasarch-1-1[1]cite-ref-griffiths-3-1[3]cite-ref-narayanan-4-1[4]

• Balance puzzlescite-ref-griffiths-3-2[3]

• River crossing puzzlescite-ref-griffiths-3-3[3]cite-ref-narayanan-4-2[4]

• The Tower of Hanoicite-ref-narayanan-4-3[4]

• Finding the missing element in a data streamcite-ref-gasarch-1-2[1]

• The geometric median problem for Manhattan distancecite-ref-gasarch-1-3[1]

The puzzles in the book cover a wide range of difficulty, and in general do not require more than a high school level of mathematical background.cite-ref-griffiths-3-4[3] William Gasarch notes that grouping the puzzles only by their difficulty and not by their themes is actually an advantage, as it provides readers with fewer clues about their solutions.cite-ref-gasarch-1-4[1]

Reviewer Narayanan Narayanan recommends the book to any puzzle aficionado, or to anyone who wants to develop their powers of algorithmic thinking.cite-ref-narayanan-4-4[4] Reviewer Martin Griffiths suggests another group of readers, schoolteachers and university instructors in search of examples to illustrate the power of algorithmic thinking.cite-ref-griffiths-3-5[3] Gasarch recommends the book to any computer scientist, evaluating it as "a delight".cite-ref-gasarch-1-5[1]

cite-note-gasarch-11. ↑ citerefgasarch2013Gasarch, William (December 2013), "Review of Algorithmic Puzzles" (PDF), ACM SIGACT News, 44 (4): 47–48, doi:10.1145/2556663.2556674

cite-note-rosebrock-22. ↑ citerefrosebrockRosebrock, Stephan, "Review of Algorithmic Puzzles", zbMATH, Zbl 1233.00005

cite-note-griffiths-33. ↑ citerefgriffiths2014Griffiths, Martin (March 2014), "Review of Algorithmic Puzzles", The Mathematical Gazette, 98 (541): 188, doi:10.1017/S0025557200001182, JSTOR 24496640

cite-note-narayanan-44. ↑ citerefnarayanan2012Narayanan, Narayanan (2012), "Review of Algorithmic Puzzles", Mathematical Reviews, MR 2866446